package com.heima.leetcode.datastructure.binarysearchtree;

import java.util.LinkedList;
import java.util.concurrent.atomic.AtomicLong;

/**
 * <strong>是否是一个合理的二叉搜索树</strong>
 *
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/11 16:34
 */
public class IsValidBST {

    /**
     * <h3>方法一：中序遍历比较相邻节点（非递归）</h3>
     *
     * @param root 树的根节点
     * @return 是有效的二叉搜索树返回true
     */
    public static boolean isValidBST1(TreeNode root) {
        TreeNode curr = root;
        TreeNode lastNode = null;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode last = stack.pop();
                if (lastNode != null) {
                    if (last.val <= lastNode.val) {
                        return false;
                    }
                }
                lastNode = last;
                curr = last.right;
            }
        }
        return true;
    }

    static long lastValue = Long.MIN_VALUE;

    /**
     * <h3>方法二：中序遍历比较相邻节点（递归）</h3>
     *
     * @param root 当前树的根节点
     * @return 是有效的二叉搜索树返回true
     */
    public static boolean isValidBST2(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST2(root.left)) {
            return false;
        }
        if (root.val <= lastValue) {
            return false;
        }
        lastValue = root.val;
        return isValidBST2(root.right);
    }

    /**
     * <h3>方法三：中序遍历比较相邻节点（递归）</h3>
     *
     * @param root 当前树的根节点
     * @return 是有效的二叉搜索树返回true
     */
    public static boolean isValidBST3(TreeNode root) {
        return isValid1(root, new AtomicLong(Long.MIN_VALUE));
    }

    /**
     * 方法三的递归实现
     *
     * @param root 当前树根节点
     * @param prev 记录上一次的值，不能用Long，Long是不可变类型
     * @return 有效返回true
     */
    private static boolean isValid1(TreeNode root, AtomicLong prev) { // 参数里的局部变量只能往深处传，从深处传回来需要return，或者设置静态变量，或者传一个对象的引用（引用的对象的内部包装的有什么东西是可以更改的，比如数组啥的），递归传过去传过来引用的同一个对象
        if (root == null) {
            return true;
        }
        if (!isValid1(root.left, prev)) {
            return false;
        }
        if (root.val <= prev.get()) {
            return false;
        }
        prev.set(root.val);
        return isValid1(root.right, prev);
    }

    /**
     * <h3>方法四：上下界递归比较法</h3>
     *
     * @param root 树的根节点
     * @return 如果有效则返回true
     */
    public static boolean isValidBST4(TreeNode root) {
        return isValid2(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    /**
     * 方法四的递归实现
     *
     * @param root 当前树的根节点
     * @param min  当前根节点的取值下限
     * @param max  当前根节点的取值上限
     * @return 如果当前子树是有效的二叉搜索树则返回true
     */
    private static boolean isValid2(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }
        if (root.val <= min || root.val >= max) {
            return false;
        }
        return isValid2(root.left, min, root.val) && isValid2(root.right, root.val, max);
    }
}
